package com.example.hot100;

import com.example.tree.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。
 *
 *  示例 1:
 * Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
 * Output: [3,9,20,null,null,15,7]
 *
 *  示例 2:
 * Input: preorder = [-1], inorder = [-1]
 * Output: [-1]
 */
public class Leetcode105_BuildTree {
    public static void main(String[] args) {

        int[] preOrder = new int[] {3, 9, 20, 15, 7};
        int[] inOrder = new int[] {9, 3, 15, 20, 7};
        TreeNode root = new Solution().buildTree(preOrder, inOrder);

    }

    static class Solution {
        /**
         * 迭代方式创建
         * @param preorder
         * @param inorder
         * @return
         */
        public TreeNode buildTree2(int[] preorder, int[] inorder) {
            return null;
        }

        /**
         * 递归方式创建
         * 前序遍历的第一个节点就是树的根节点，然后根据这个节点在中序遍历中找到中序的根节点的位置就可以将中序切成
         * 左子树序列 + 根 + 右子树序列
         * 依次递归
         * @param preorder
         * @param inorder
         * @return
         */
        public TreeNode buildTree1(int[] preorder, int[] inorder) {
            Map<Integer, Integer> inorderMap = new HashMap<>(); // 方便直接检索中序遍历的元素位置
            for (int i = 0; i < inorder.length; i++) {
                inorderMap.put(inorder[i], i);
            }

            return buildTreeByRecursion(preorder, 0, preorder.length - 1,
                    inorderMap, 0, inorder.length - 1);
        }

        private TreeNode buildTreeByRecursion(int[] preorder, int preLeft, int preRight,
                                              Map<Integer, Integer> inorderMap, int inLeft, int inRight) {
            if (preLeft > preRight) return null;

            int inRootIndex = inorderMap.get(preorder[preLeft]);// 前序遍历的开始就是根节点,在中序遍历中找到该节点的位置
            TreeNode root = new TreeNode(preorder[preLeft]); //构建根节点
            int leftChildSize = inRootIndex - inLeft;
            // 递归构造左子树并挂在根节点的左子树上
            root.left = buildTreeByRecursion(preorder, preLeft + 1, preLeft + leftChildSize,
                    inorderMap, inLeft, inRootIndex - 1);
            // 递归地构造右子树，并挂在根节点右子树上
            root.right = buildTreeByRecursion(preorder, preLeft + leftChildSize + 1, preRight,
                    inorderMap, inRootIndex +1, inRight);

            return root;
        }

        public TreeNode buildTree(int[] preorder, int[] inorder) {
            return buildTree1(preorder, inorder);
        }
    }
}
